package com.lun.easy;

import java.util.ArrayList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class FindModeinBinarySearchTree {
	//方法一：需要O(n)空间
    public int[] findMode(TreeNode root) {
        List<Integer> result = new ArrayList<>(), list = new ArrayList<>();
    	recurse(root, list);
    	
    	int maxCount = 0, startIndex = 0;
    	int lastNum = list.get(startIndex);
    	for(int i = 1; i <= list.size(); i++) {
    		if(i == list.size() || list.get(i) != lastNum) {
    			int count = i - startIndex;
    			if(count > maxCount) {
    				maxCount = count;
    				result.clear();
    				result.add(lastNum);
    			}else if(count == maxCount){
    				result.add(lastNum);
    			}
    			startIndex = i;
    			if(i < list.size())
    				lastNum = list.get(i);
    		}
    	}
    	
    	return result.stream()
				   .mapToInt(Integer::intValue)
				   .toArray();
    }
    
    private void recurse(TreeNode node, List<Integer> list) {
    	if(node == null)
    		return;
    	recurse(node.left, list);
    	list.add(node.val);
    	recurse(node.right, list);
    }
    
    
    
    //方法二：无需额外O(n)空间
    public int[] findMode2(TreeNode root) {
    	List<Integer> result = new ArrayList<>();
    	Integer[] array = {null, 0, 0};//{lastNum, count, maxCount}
    	recurse2(root, array, result);
    	updateCount(array, result);
    	return result.stream()
				   .mapToInt(Integer::intValue)
				   .toArray();
    }
    
    private void recurse2(TreeNode node, Integer[] array, List<Integer> result) {
    	if(node == null)
    		return;
    	recurse2(node.left, array, result);
    	
    	int current = node.val;
    	if(array[0] == null) { //初始化
    		array[0] = current;
    		array[1] = array[2] = 1;
    	}else {
    		if(current != array[0]) {
    			updateCount(array, result);
    			array[0] = current;
    			array[1] = 0;
    		}
    		array[1]++;
    	}
    	
    	recurse2(node.right, array, result);
    }
    
    private void updateCount(Integer[] array, List<Integer> result) {
		if(array[1] > array[2]) {
			array[2] = array[1];
			result.clear();
			result.add(array[0]);
		}else if(array[1] == array[2]){
			result.add(array[0]);
		}
    }
    
}
